import heapq
from typing import List


def count_num(lst):
    """根据[[l1,r1],[l2,r2]]线段列表，计算线段总长度（重合部分只记一次）"""
    if not lst:
        return 0

    lst.sort()

    ans = 0
    s, e = lst[0]
    for i in range(1, len(lst)):
        l, r = lst[i]
        if l > e:
            ans += e - s
            s, e = l, r
        else:
            e = max(e, r)
    ans += (e - s)
    return ans


class Solution:
    _MOD = 10 ** 9 + 7

    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        rectangles.sort(key=lambda x: (x[0], x[2]))
        # print(rectangles)

        # 坐标压缩
        coords = set()
        for x1, y1, x2, y2 in rectangles:
            coords.add(x1)
            coords.add(x2)
        coords = sorted(coords)

        i = 0  # 当前长方形列表的遍历位置
        now = []  # 当前位置所有长方形右边、下边、上边

        ans = 0
        for j in range(len(coords) - 1):
            d = coords[j + 1] - coords[j]

            while i < len(rectangles) and rectangles[i][0] == coords[j]:
                heapq.heappush(now, (rectangles[i][2], rectangles[i][1], rectangles[i][3]))
                i += 1

            while now and now[0][0] == coords[j]:
                heapq.heappop(now)

            # print(j, coords[j], ":", now, "*", d, "=", count_num([[y1, y2] for x2, y1, y2 in now]), "*", d)

            ans += count_num([[y1, y2] for x2, y1, y2 in now]) * d

        return ans % self._MOD


if __name__ == "__main__":
    #  6
    print(Solution().rectangleArea([[0, 0, 2, 2], [1, 0, 2, 3], [1, 0, 3, 1]]))

    # 49
    print(Solution().rectangleArea([[0, 0, 1000000000, 1000000000]]))

    # 测试用例3: 7
    print(Solution().rectangleArea([[0, 0, 2, 2], [1, 1, 3, 3]]))

    # 测试用例5: 2
    print(Solution().rectangleArea([[0, 0, 1, 1], [2, 2, 3, 3]]))

    # 测试用例6: 1550
    print(Solution().rectangleArea([[25, 20, 70, 27], [68, 80, 79, 100], [37, 41, 66, 76]]))

    # 测试用例22: 3108
    print(Solution().rectangleArea([[22, 24, 67, 34], [23, 18, 39, 41], [10, 63, 80, 98]]))
